The present invention relates to optimizing data flow over a packet-switched computer network, and more specifically to a method of optimizing data flow under conditions of network congestion using delay-based congestion control.
Delay-based congestion control methods have significant advantages over many of the loss-based mechanisms in Transmission Control Protocol (TCP). Most loss-based congestion detection systems do not distinguish between random loss events and those caused by congestion. Under the additive-increase-multiplicative-decrease (AIMD) congestion control paradigm, random loss events often result in network underutilization. Single-bit loss information does not directly measure congestion. On a modern network with ample packet buffers between transfer nodes, congestion can accumulate to a significant level at the link bottleneck before a single packet is dropped. In contrast, delay-based congestion measurements detect congestion as it happens and can be less impacted by random events.
One of the most prominent delay-based congestion control mechanisms is “FAST TCP”, which provides a framework for building a high-speed transfer protocol. In theory, FAST TCP offers many benefits (besides high speed transfer), such as fairness and stability. However, its behavior in the real-world network environment is not so clear, especially in the presence of feedback delay.
Feedback delay is the lag between the present network congestion condition and the input signal for the rate control unit. Such feedback delay can arise from congestion itself, processing delay due to hardware or implementation artifacts etc. The lag can retard the rate control response to congestion, leading to the oscillation of data flow rate, excessive queueing delay and packet loss, hence destabilizing transfers. More significant repercussions can be expected on a large scale network. Many efforts have been devoted to deriving analytical restrictions on the parameters to tune the algorithm in order to achieve stability. Most studies have focused on the local stability conditions with zero feedback delay or other simplification of a feedback model. It has reached the consensus that that the feedback delay is responsible for the instability, however, whether or not such theoretical models resemble realistic behavior in the real world applications are still open to questions given the complex activities of modern network. Deriving a robust stability condition beyond zero feedback-delay approximation is still a challenging problem.
Multiple factors can contribute to feedback delay during a transfer. Two most important sources of the feedback delay are: 1) feedback delay due to the communication between client and server during measurement and rate-update, and 2) the numerical artifact introduced in signal filtering.
For an end-to-end protocol, the client and server constantly exchange packets to measure the round-trip-time (RTT), which are used to calculate the queueing delay. This measurement, by definition, is a delayed signal and it always lags behind the instantaneous queueing delay, which is the queueing delay a packet would experience if the packet enters the network at the moment. The difference between the measured and instantaneous queueing delay varies in time and is apparently greater as congestion increases. Depending on the implementation of the protocol, additional feedback delay can be introduced when syncing the sender and receiver for a rate-update. For example, if the RTT is measured by the receiver and the rate is applied at the sender, then the sender must wait for the receiver to transmit the rate-update data back to sender, adding at least a one-way propagation time to the total feedback delay.
Raw RTT measurements are usually filtered to reduce noise, but this filtered data may misrepresent the trend of the original measurements, distorting the input for congestion control. Exponential moving average methods have been widely accepted in the development of TCP, including the fixed-weight Jacobson's filter and dynamic-weight exponential filters such as the one in FAST TCP and Eifel algorithm. These methods require only the latest measurement to update the result, which saves memory and is easy to implement. Though the RTT data can be smoothed by averaging over time, a moving average produces artificial lag when the signal is trending.